/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/largest-divisible-subset
   @Language: C++
   @Datetime: 19-06-10 11:56
   */

class Solution {
public:
	/*
	 * @param nums: a set of distinct positive integers
	 * @return: the largest subset 
	 */
	vector<int> largestDivisibleSubset(vector<int> &nums) {
		// write your code here
		sort(nums.begin(),nums.end());
		vector<int> dp(nums.size(),1), path(nums.size(),0);
		int pos=0, len=0;
		for(int i=0; i<nums.size(); ++i){
			for(int j=i; j--;){
				if(nums[i]%nums[j]==0 && dp[i]<dp[j]+1){
					dp[i]=dp[j]+1;
					path[i]=j;
				}
			}
			if(dp[i]>len){
				pos=i;
				len=dp[i];
			}
		}
		vector<int> res(len,0);
		for(int i=len; i--; pos=path[pos])
			res[i]=nums[pos];
		return res;
	}
};
